//问题 C: 【数据结构2-6】创建有序单链表
//时间限制: 1 Sec  内存限制: 128 MB
//提交: 3795  解决: 2356
//[提交][状态][论坛]
//题目描述
//根据输入的整数，创建单链表，并保持链表中元素值递增排序。
//
//输入
//输入正整数，以-1结束
//
//输出
//按链表顺序从头到尾输出链表，一个空格间隔
//
//样例输入
//4 6 3 1 2 5 -1
//样例输出
//1 2 3 4 5 6 

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
	int data;
	struct Node *next;
} node;

node* creatlink() {
	 node *head=NULL;
	int n;
	 node *q,*p;
	while(1) {
		scanf("%d",&n);
		if(n==-1) {
			break;
		}
		int flag=0;
		p=( node *) malloc(sizeof( node));

		p->data=n;
		//空 创建
		if(head==NULL) {
			p->next=NULL;
			
			q=(node *)malloc (sizeof(node));
			q->data=0;
			q->next=p;
			head=q;
		} else {
			 node *t;
			t=head;

			//循环判断插入的位置
			//1. 头插
			if(t->data>n) {
				flag=1;
				p->next=head;
				head=p;
			} else {
                //2. 中间插入
				while(t->next!=NULL) {
					if(t->next->data>n) {
						flag=1;
						p->next=t->next;
						t->next=p;
						break;
					}
					t=t->next;
				}

			}
			//3. 尾插
			if(flag==0) {
				 node *t;
				t=head;
				p->next=NULL;
				while(t->next!=NULL){
					t=t->next;
				}
				t->next=p;
			}
			
		}
	}
	return head;
}
void traverse(node* head) {
	node *p;
	if (head==NULL) return;
	p=head->next;
	while(p) {
		printf("%d ",p->data);
		p=p->next;
	}
}
int main() {
	node *head;
	head=creatlink();
	traverse(head);
}